package de.h_da.fbi.cg.pointcloud.util;

import java.util.List;

/**
 * @author Nicolas Gramlich
 * @since 23:28:22 - 11.11.2010
 */
public class Quicksort {
	// ===========================================================
	// Constants
	// ===========================================================

	// ===========================================================
	// Fields
	// ===========================================================

	// ===========================================================
	// Constructors
	// ===========================================================

	// ===========================================================
	// Getter & Setter
	// ===========================================================

	// ===========================================================
	// Methods for/from SuperClass/Interfaces
	// ===========================================================

	// ===========================================================
	// Methods
	// ===========================================================

	public static <T extends Comparable<T>> void sort(final List<T> pData) {
		final int size = pData.size();
		if(size == 0) {
			return;
		}
		Quicksort.quicksort(pData, 0, size - 1);
	}

	private static <T extends Comparable<T>> void quicksort(final List<T> pData, final int pLeft, final int pRight) {
		int i = pLeft;
		int j = pRight;
		final T pivot = pData.get(pLeft + (pRight - pLeft) / 2);

		while(i <= j) {
			while(pData.get(i).compareTo(pivot) < 0) {
				i++;
			}
			while(pData.get(j).compareTo(pivot) > 0) {
				j--;
			}
			if(i <= j) {
				final T temp = pData.get(i);
				pData.set(i, pData.get(j));
				pData.set(j, temp);
				i++;
				j--;
			}
		}
		if(pLeft < j) {
			Quicksort.quicksort(pData, pLeft, j);
		}
		if(i < pRight) {
			Quicksort.quicksort(pData, i, pRight);
		}
	}

	// ===========================================================
	// Inner and Anonymous Classes
	// ===========================================================
}